package 牛客.动态规划;

public class 力扣416分割等和子集 {
    public boolean canPartition(int[] nums) {
        //分析题，克制能否分割成两个等和子集，即整个数组的和sum/2=子集和
        if (nums.length<2) {
            //不能分割成 两个子集
            return false;
        }
        int sum=0;
        for (int x:nums) {
            sum+=x;
        }
        if (sum%2!=0) {
            //和为奇数，则不可能分成两个 等和子集
            return false;
        }

        int target=sum/2;
        int[][] dp=new int[nums.length][target+1];
        //dp[i][j] 代表 0-i下标的元素之和是否等于j
        for (int i = 1; i <nums.length; i++) {
            for (int j = 0; j <target+1; j++) {
                if (j<nums[i]) {
                    dp[i][j]=dp[i-1][j];
                }
                if (j>=nums[i]) {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
                }
            }
        }

        if (dp[nums.length-1][target]==target) {
            return true;
        }
        return false;

    }
}
